package com.lw.leetcode.stack.b;

/**
 * stack
 * 665. 非递减数列
 *
 * @Author liw
 * @Date 2021/7/6 13:12
 * @Version 1.0
 */
public class CheckPossibility {

    public static void main(String[] args) {
        CheckPossibility test = new CheckPossibility();
//        int[] arr = {1,4,3,4,5,1000,7,8,9,10};
//        int[] arr = {5,7,2,8};
        int[] arr = {1, 1, 1};
        boolean b = test.checkPossibility(arr);
        System.out.println(b);
    }

    public boolean checkPossibility(int[] nums) {
        int length = nums.length;
        int[] arr = new int[length];
        int index = 1;
        arr[0] = nums[0];
        int limit = 1;
        for (int i = 1; i < length; i++) {
            int value = nums[i];
            if (value >= arr[limit - 1]) {
                arr[limit++] = value;
            } else {
                index = limit - 1;
                while (index != -1 && arr[index] > value) {
                    index--;
                }
                arr[index + 1] = value;
            }
        }
        return limit >= length - 1;
    }

}
